#include <iostream>
#include <string.h>
#include <math.h>

int backpack01(int weight, int n, int wt[], int val[]){
    //weight背包容量，n物品的个数，wt[]物品的重量数组，val[]物品的价值数组
    int dp[weight+1];
    memset(dp, 0, sizeof(dp));
    //先遍历物品
    for (int i = 0; i < n; i++) {
        //再遍历容量，倒序遍历，注意！遍历的背包容量j是>=当前的物品的重量的。
        for (int j = weight; j >= wt[i]; j--) {
            dp[j] = fmax(dp[j], dp[j - wt[i]] + val[i]);
        }
    }
    return dp[weight];
}

int main(){

    using namespace std;
    int weight = 3;
    int n = 3;
    int wt[3] = {2, 1, 3};
    int val[3] = {4, 2, 5};
    cout << backpack01(weight, n, wt, val) << endl;
    return 0;
}